﻿#include<stdlib.h>
#include<time.h>
#include"Sort.h"
void test()
{
	vector<int> v{ 4,5,1,3,9,7,6,8,2,0 };
	Heap<int> heap;
	heap.heap_sort(v, 10);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}


void TestTopk()
{
	Heap<int,Greater<int>> heap;
	int n = 1000000;
	vector<int> v;
	srand(time(0));
	for (size_t i = 0; i <n; ++i)
	{
		v.push_back( rand() %1000000);
	}
	v[33] = 10000000 + 1;
	v[12] = 10000000 + 2;
	v[21] = 10000000 + 3;
	v[19] = 10000000 + 4;
	v[15] = 10000000 + 5;
	v[23] = 10000000 + 6;
	v[48] = 10000000 + 7;
	v[27] = 10000000 + 8;
	v[42] = 10000000 + 9;
	v[31] = 10000000 + 10;
	heap.topk(v, 10);
	int i = 0;
	for (size_t i = 0; i < 10; ++i)
	{
		cout << v[i] << " " << endl;
	}

	//PrintTopK(a, n, 10);
}

void test_SGI_STL_sort()
{
	int a1[] = {4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11
		, 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2
		,0,11 , 4,5,1,3,9,7,6,8,2,0,11 };

	int a2[] = {4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11
		, 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2
		,0,11 , 4,5,1,3,9,7,6,8,2,0,11 };

	int a3[] = { 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2,0,11
		, 4,5,1,3,9,7,6,8,2,0,11 , 4,5,1,3,9,7,6,8,2
		,0,11 , 4,5,1,3,9,7,6,8,2,0,11 ,1,1,1};


	int n = sizeof(a1) / sizeof(int);
	sort_threeway_division1(a1, 0, n - 1);
	//zwy::heap_sort(a2, n);
	//zwy::insert_sort(a3, n);
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a1[i]);
	}
	/*for (int i = 0; i < n; ++i)
	{
		printf("%d ", a2[i]);
	}*/
	/*for (int i = 0; i < n; ++i)
	{
		printf("%d ", a3[i]);
	}*/
	
}

void TestOP1()
{
	srand(time(0));
	const int N = 10000000;
	int depthLimit = 2 * log10(N);
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand()+i;
		a2[i] = rand()+i;
		a3[i] = rand()+i;
		a4[i] = rand()+i;
		a5[i] = rand();
		a6[i] = rand();
		
	}
	int begin1 = clock();
	SGI_STL_sort(a1, 0,N-1, depthLimit);
	int end1 = clock();
	printf("SGI_STL_sort:%d\n", end1 - begin1);


	int begin2 = clock();
	sort_frpoint(a2, 0, N - 1);
	int end2 = clock();
	printf("sort_frpoint:%d\n", end2 - begin2);
	int i = 0;


	int begin3 = clock();
	sort_hoare(a3, 0, N - 1);
	int end3= clock();
	printf("sort_hoare:%d\n", end3 - begin3);
	
	
	int begin4 = clock();
	sort_digging(a4, 0, N - 1);
	int end4 = clock();
	printf("sort_digging:%d\n", end4 - begin4);

	int begin5 = clock();
	sort_threeway_division1(a5, 0, N - 1);
	int end5 = clock();
	printf("sort_3division1:%d\n", end5 - begin5);

	int begin6 = clock();
	sort_threeway_division2(a6, 0, N - 1);
	int end6 = clock();
	printf("sort_3division2:%d\n", end6 - begin6);


	/*for (int i = 0; i < N; ++i)
	{
		printf("%d ", a6[i]);
	}*/
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	
}

int main()
{
	TestOP1();
	//test_SGI_STL_sort();
	//test();
	//TestTopk();
	//test_insert_sort();
	return 0;
}


